package com.lsa.letcode.the48.rotateImg;

public class Solution {
    public void rotate(int[][] matrix) {
    	int[] coords = new int[2];
    	int[] origin = new int[2]; // upper left of the matrix
    	int[] seq = new int[4];
    	
    	int n = matrix.length;
    	int subSize = n;
    	for (int x = 0; x < n / 2; x++) {
    		origin[0] = x;
			origin[1] = x;
			for (int y = origin[1]; y < origin[1] + subSize - 1; y++) {
				coords[0] = origin[0];
    			coords[1] = y;
    			for (int i = 0; i < 4; i++) {
    				seq[i] = get(matrix, coords);
    				nextCoords(origin, subSize, coords, subSize - 1, coords);
    			}
    			cyclicShiftRight(seq);
    			coords[0] = x;
    			coords[1] = y;
    			for (int i = 0; i < 4; i++) {
    				set(matrix, coords, seq[i]);
    				nextCoords(origin, subSize, coords, subSize - 1, coords);
    			}
			}
			subSize -= 2;
    	}
    }
    
    int get(int[][] matrix, int[] coords) {
    	return matrix[coords[0]][coords[1]];
    }
    
    void set(int[][] matrix, int[] coords, int val) {
    	matrix[coords[0]][coords[1]] = val;
    }
    
    void cyclicShiftRight(int[] seq) {
    	int prev = seq[0];
    	for (int i = 0; i < seq.length; i++) {
    		int j = (i + 1) % seq.length;
			int t = seq[j]; 
			seq[j] = prev;
			prev = t;
		}
    }
    
    void nextCoords(int[] origin, int n, int[] pair, int step, int[] result) {
    	int n2 = (coordsToN2(origin, n, pair) + step) % (4 * n);
    	n2ToCoords(origin, n, n2, result);
    }
    
    void n2ToCoords(int[] origin, int n, int n2, int[] coords) {
    	n2 = n2 % (4 * n);
    	
    	if (-1 < n2 && n2 < n - 1) {
    		coords[0] = origin[0];
    		coords[1] = origin[1] + n2;
    	}
    	else if (n - 2 < n2 && n2 < 2 * n - 2) {
    		coords[0] = origin[0] + n2 - (n - 1);
    		coords[1] = origin[1] + n - 1;
    	}
    	else if (2 * n - 3 < n2 && n2 < 3 * n - 3) {
    		coords[0] = origin[0] + n - 1;
    		coords[1] = origin[1] + n - 1 - (n2 - (2*n - 2));
    	}
    	else if (3 * n - 4 < n2 && n2 < 4 * n - 4) {
    		coords[0] = origin[0] + n - 1 - (n2 - (3*n - 3));
    		coords[1] = origin[1];
    	}
    }
    
    int coordsToN2(int[] origin, int n, int[] pair) {
    	// translate to (0,0)
    	int x = pair[0] - origin[0];
    	int y = pair[1] - origin[1];
    	
    	if (x == 0 && y < n - 1) {
    		return y;
    	}
    	else if (y == n - 1 && x < n - 1) {
    		return n - 1 + x;
    	}
    	else if (x == n - 1 && y > 0) {
    		return 3*n - 3 - y;
    	}
    	else { // y == 0
    		return 4*n - 4 - x;
    	}
    }
}